package OptimalAlgorithm.DivideAndConquer_Merge;
//https://leetcode.cn/problems/sort-an-array/description/
public class SortArray {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length - 1);
        return nums;
    }
    private void mergeSort(int[] nums,int left ,int right){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);//合并两个有序数组
        merge(nums,left,mid,right);
    }
    //合并两个有序数组
    private void merge (int[] nums,int left,int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] temp = new int[right - left + 1];
        int index = 0;
        while (s1 <= e1 && s2 <= e2){
            if(nums[s1] > nums[s2]){
                temp[index++] = nums[s2++];
            }else {
                temp[index++] = nums[s1++];
            }
        }
        while (s1 <= e1){
            temp[index++] = nums[s1++];
        }
        while (s2 <= e2){
            temp[index++] = nums[s2++];
        }
        for (int i = left; i <= right ; i++) {
            nums[i] = temp[i - left];
        }
    }
}
